Cut-and-stitch: efficient parallel learning of linear dynamical systems on smps
Lei Li
Wenjie Fu
Fan Guo
Todd C. Mowry
Christos Faloutsos
Multi-core processors with ever increasing number of cores per chip are becoming prevalent in modern parallel computing. Our goal is to make use of the multi-core as well as multi-processor architectures to speed up data mining algorithms. Specifically, we present a parallel algorithm for approximate learning of Linear Dynamical Systems (LDS), also known as Kalman Filters (KF). LDSs are widely used in time series analysis such as motion capture modeling, visual tracking etc. We propose <i>Cut-And-Stitch</i> (CAS), a novel method to handle the data dependencies from the chain structure of hidden variables in LDS, so as to parallelize the EM-based parameter learning algorithm. We implement the algorithm using OpenMP on both a supercomputer and a quad-core commercial desktop. The experimental results show that parallel algorithms using <i>Cut-And-Stitch</i> achieve comparable accuracy and almost linear speedups over the serial version. In addition, <i>Cut-And-Stitch</i> can be generalized to other models with similar linear structures such as Hidden Markov Models (HMM) and Switching Kalman Filters (SKF).
